P6218 [USACO06NOV] Round Numbers S

发布于 2020-09-05 | 分类于数位dp | 2分钟 | 324字数

首先有个想法，如果该位为 $0$ 且不是前导 $0$ ，则将 $0$ 的数量加一，最后看 $0$ 是否出现了至少 $\lceil \frac{\text{len}}{2} \rceil$ 次。

但这样有个问题，比如在 $n=8(1000)_2$ 时， $2(0010)$ 就不会被计入答案，原因是 $2$ 的前导 $0$ 也算在了它二进制的位数中。

所以还要记录前导零的数量 $\text{leadnum}$ ，最后判断是否出现至少 $\lceil \frac{\text{len}-\text{leadnum}}{2} \rceil$ 即可。

SP17247 Digit Sum

发布于 2020-09-05 | 分类于数位dp | 2分钟 | 304字数

每个数的数字和的和其实就是所有数字与它出现次数的积的和。

那么对于 $0-9$ ，依次像 P2602 [ZJOI2010]数字计数统计出现次数就可以了。

具体做法也很简单，记录前 $pos$ 位某个数字出现次数 $sum$ ，记忆化搜索即可通过。

发布于 2020-09-05 | 分类于生成函数 | 4分钟 | 551字数

设整数 $n$ 的 $\text{lqp}$ 拆分权值为 $g(n)$ , 那么有：

\begin{cases} g(n)=1 & (n=0) \\

发布于 2020-07-14 | 分类于莫比乌斯反演 | 6分钟 | 934字数

\sum_{i=1}^n\sum_{j=i+1}^n\text{lcm}(A_i,A_j)

\frac{\sum_{i=1}^n\sum_{j=1}^n\text{lcm}(A_i,A_j)-\sum_{i=1}^nA_i}{2}